<html>
<head>
<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Describing Structure and Semantics of Graphs Using an RDF Vocabulary</title>
</head>
<body alink="#662222" vlink="#662222" link="#662222" bgcolor="#EFFFEF">
<table cellpadding="8" cellspacing="4" width="100%" border="0">
<tr>
<td bgcolor="#BADABA" align="right"><span style="font-size:140%;font-face:sans-serif"><i><b>Extreme</b></i> Markup Languages</span></td>
</tr>
</table>
<h1>Describing Structure and Semantics of Graphs Using an RDF Vocabulary</h1>
<address>John Punin<br class="br">Rensselaer Polytechnic Institute<br class="br">Department of Computer Science<br class="br">
<a href="mailto:puninj@cs.rpi.edu">puninj@cs.rpi.edu</a>
</address>
<br class="br">
<address>Mukkai Krishnamoorthy<br class="br">Rensselaer Polytechnic Institute<br class="br">Department of Computer Science<br class="br">
<a href="mailto:moorthy@cs.rpi.edu">moorthy@cs.rpi.edu</a>
</address>
<p>
<b>Keywords: </b>RDF; XML; RGML; Graph Structure; Metadata; Webgraph</p>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<h5>
<i>Abstract</i>
</h5>

<p>
The RDF Graph Modeling Language (RGML) is a W3C RDF vocabulary to describe 
graph structures, including semantic information associated with a graph. 
Viewing general graphs as Web resources, RGML defines graph, node, and edge 
as RDF classes and attributes of graphs (such as label and weight) as RDF 
properties. Some of these RDF properties establish relationships between 
graph, node, and edge instances. RDF Statements about graph elements involve 
subjects, predicates and objects. Subjects and predicates are RDF Resources, 
while objects are either RDF Resources or RDF Literals. RGML 
uses the XML Schema datatypes for RDF Literals. RGML can be easily combined 
with other RDF  vocabularies, for example, to add Dublin Core properties. 
RGML is very useful for describing webgraphs (the structure of a web site), 
web collections, and sitemaps.
</p>

</td>
</tr>
</table>

<div class="local-name()">

<h2>1 Introduction</h2>

<p>
We present the RDF Graph Modeling Language (RGML),  a W3C RDF vocabulary 
<b><span style="font-size:85%"><a name="fromrdf" href="#rdf">[RDF]</a></span></b> to describe graph structures. General graphs can be 
seen as Web resources. 
RGML defines graph, node, and edge as  RDF classes
and attributes of graphs, such as label and weight, as RDF properties. 
Some of these RDF properties establish relationships between graph, node, 
and edge instances. Hence, a graph instance "knows" which node and edge 
instances belong to this graph. There is no restriction on the number of 
graph, node, and edge instances that can be defined in a RGML file.  Neither
is there a restriction about nodes and edges shared between several graphs.
Graphs can be included in other graphs; such graphs are called subgraphs. 
We use RDF Schema <b><span style="font-size:85%"><a name="fromrdfs" href="#rdfs">[RDFS]</a></span></b> to provide with the definition of RGML classes and properties.  
RGML can be easily combined with other RDF vocabularies to add new 
properties, for example, you can add a Dublin Core <b><span style="font-size:85%"><a name="fromdc" href="#dc">[DC]</a></span></b> 
dc:title property to a node instance to assign a string title to a node.
</p>

<p>
Several examples in this paper show how easy it is to describe different 
kind of graphs using the RGML vocabulary.  Our main interest is to describe
webgraphs <b><span style="font-size:85%"><a name="fromwwwpal" href="#wwwpal">[WWWPAL]</a></span></b>.  A webgraph describes the structure of
a web site where the nodes are web pages and the edges are hyperlinks.  We 
use the Dublin Core <b><span style="font-size:85%"><a name="fromdc" href="#dc">[DC]</a></span></b> vocabulary to add information to 
nodes (web pages) such as dc:title (title of the web page), dc:format 
(mime of the web page), and dc:date (date of creation of the web page). 
Using RGML we can also define web collections (a collection of web pages 
that represent one document) as subgraphs of a webgraph.  Site-maps can also
be seen as graph instances; hence RGML is a good candidate for describing 
site-maps.
</p>

</div>

<div class="local-name()">

<h2>2 Motivation</h2>

<p>
XML <b><span style="font-size:85%"><a name="fromxml" href="#xml">[XML]</a></span></b> and XML Schema <b><span style="font-size:85%"><a name="fromxmlschema" href="#xmlschema">[XMLSCHEMA]</a></span></b> 
provide a syntactic description of an underlying document.
The existing XML vocabularies designed to describe graph structures 
<b><span style="font-size:85%"><a name="fromgraphxml" href="#graphxml">[GRAPHXML]</a></span></b> <b><span style="font-size:85%"><a name="fromgxl" href="#gxl">[GXL]</a></span></b> <b><span style="font-size:85%"><a name="fromxgmml" href="#xgmml">[XGMML]</a></span></b>
provide a means to describe structural information 
about nodes, edges, subgraphs, etc.  RGML, based on the W3C RDF/XML model, 
describes the semantics of graphs, as well as structural information.  RGML
files are written with the XML syntax and the 
semantics use the RDF model. 
By using RGML, one can describe the graph structures and add 
statements to describe the elements of the graph.  Two graphs may have the 
same structure even though one may describe network topology while the other 
may describe a web site.  The metadata related to these graphs are different.
The RDF model permits the combination of different metadata using XML 
Namespaces <b><span style="font-size:85%"><a name="fromxmlns" href="#xmlns">[XMLNS]</a></span></b>, so it is possible to differentiate between several types 
of graphs.  RGML describes the semantics of an abstract graph based on the 
appropriate vocabulary. So, for example, when we describe a webgraph, we use 
the vocabulary of dublin core. The most interesting aspect of RGML is that 
the semantics of an arbitrary graph can be specified using RDF.
</p>

</div>

<div class="local-name()">

<h2>3 RGML Datatypes</h2>

<p>
RDF Statements about graph elements involve subjects, predicates and 
objects.  Subjects and predicates are RDF Resources, while objects are 
either RDF Resources or RDF Literals. It is not possible to distinguish the
datatypes of RDF Literal values and hence RGML adopts the XML schema datatypes. RGML  
follows the same syntax given by DAML+OIL ontology markup language
<b><span style="font-size:85%"><a name="fromdaml" href="#daml">[DAML]</a></span></b>. The core 
RGML datatypes are integer, boolean and string datatypes.  These datatypes 
are the range (properties map from a domain to range.) for some RGML 
properties.
</p>

</div>

<div class="local-name()">

<h2>4 RGML Classes</h2>

<p>
The RGML classes of a general graph are Graph, Node, and Edge. Properties 
of these classes allow to establish relationship of these three classes. 
This will enable a graph instance which relates with several node and edge 
instances. Two node instances relate with an edge instance.
</p>

<div class="local-name()">

<h3>4.1 Graph Class</h3>

<p>
The Graph class is a RDF class that 
defines a general graph. This is the Graph
class that is the domain of the RDF properties: label and directed. The nodes and edges RDF properties help to relate instances of the Graph class with instances of Node and Edge classes.  Other kind of graphs such as 
webgraphs, RDF graphs, and network graphs can be subclasses of this 
Graph Class.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
  &lt;rdfs:Class rdf:ID="Graph" 
    rdfs:label="Graph"
    rdfs:comment="A Graph Description"&gt;
    &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt;
  &lt;/rdfs:Class&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>4.2 Node Class</h3>

<p>
The Node class is an RDF class that 
defines a general node. The label and 
weight RDF properties have 
Node class as domain. All nodes of a graph
are instances of these class. Webnodes (web pages) of a webgraph can be 
subclasses of the Node class.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
  &lt;rdfs:Class rdf:ID="Node" 
    rdfs:label="Node"
    rdfs:comment="A Node Description"&gt;
    &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt;
  &lt;/rdfs:Class&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>4.3 Edge Class</h3>

<p>
The Edge class is a RDF Class that defines a general edge. The label and weight RDF properties are related to the Edge class. The source and target
RDF properties of the Edge class allow it 
to relate two node instances or, in case of a hypergraph, many node instances.
(The instances of edges that have a list of nodes are called hyperedges. A 
hyperedge is defined as a subset of a set of nodes. Graphs that contain 
hyperedges are called hypergraphs. )  Webedges (Hyperlinks) of a webgraph can
be subclasses of the Edge class.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
  &lt;rdfs:Class rdf:ID="Edge" 
    rdfs:label="Edge"
    rdfs:comment="An Edge Description"&gt;
    &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt;
  &lt;/rdfs:Class&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>

</div>


<div class="local-name()">

<h2>5 RGML Properties</h2>

<p>
The domain of the RGML properties are the Graph, Node and Edge RDF classes. These properties allow to relate instances of the RGML classes to 
build the structure of a general graph.
</p>

<div class="local-name()">

<h3>5.1 label Property</h3>

<p>
The label property is a global property for all instances of RGML classes. It gives a unique string identifier to the 
instances of the graphs, nodes and edges.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
 &lt;rdf:Property ID="label"
    rdfs:label="label"
    rdfs:comment="Text representation of the graph elements"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Node"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/&gt;
 &lt;/rdf:Property&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>5.2 directed Property</h3>

<p>
The directed property has a Boolean  range and a Graph domain. The values that can be assigned to this property are either true or false. This indicates 
whether the graph is directed or not. Mixed graphs allow directed and undirected edges in the same graph. The directed 
property also belongs to a specific edge instance to indicate whether that edge is directed or not. This edge property will allow one to describe mixed graphs.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
 &lt;rdf:Property ID="directed"
    rdfs:label="directed"
    rdfs:comment="Boolean value to indicate whether the Graph is directed or not"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#boolean"/&gt;
 &lt;/rdf:Property&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>5.3 nodes Property</h3>

<p>
The nodes property is an RDF Bag list of the node instances that belongs to the graph. This gives an idea of inclusion so we can determine what nodes 
are members of the graph. The nodes property can belong to the Edge class. The instances of edges that have a list of nodes are called hyperedges. A 
hyperedge is defined as a subset of a set of nodes. Graphs that contain hyperedges are called hypergraphs. If the hypergraph is directed, the nodes 
property of the hyperedges is an RDF Seq. The RDF Seq gives an order to the list of nodes in the hyperedge.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
 &lt;rdf:Property ID="nodes"
   rdfs:label="Nodes"
   rdfs:comment="List of the nodes belong to the graph"&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/&gt;
 &lt;/rdf:Property&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>5.4 edges Property</h3>

<p>
The edges property is an RDF Bag list of the edge instances that belongs to the graph. This gives an idea of inclusion so we can determine what edges 
are members of the graph.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
 &lt;rdf:Property ID="edges"
   rdfs:label="Edges"
   rdfs:comment="List of the edges belong to the graph"&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Bag"/&gt;
 &lt;/rdf:Property&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>5.5 graphs Property</h3>

<p>
The graphs property is an RDF Bag list of the subgraph instances of the graph parent. By using this property, we can relate subgraphs with the graph that they originated from.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
 &lt;rdf:Property ID="graphs"
   rdfs:label="Subgraphs"
   rdfs:comment="List of subgraphs belong to the graph"&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Bag"/&gt;
 &lt;/rdf:Property&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>5.6 weight Property</h3>

<p>
The weight property belongs to node and edge instances. The weight is usually a numerical value assigned to a node or edge in a weighted graph.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
 &lt;rdf:Property ID="weight"
    rdfs:label="weight"
    rdfs:comment="Value (usually numerical) to show the node or edge weight"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Node"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/&gt;
 &lt;/rdf:Property&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>5.7 source Property</h3>

<p>
The source property is used to indicate the source node instance of a edge instance.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
 &lt;rdf:Property ID="source"
    rdfs:label="source"
    rdfs:comment="The rdf:ID the source node of the edge"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/&gt;
 &lt;/rdf:Property&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>5.8 target Property</h3>

<p>
The target property is used to indicate the target node instance of an edge instance.
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
 &lt;rdf:Property ID="target"
    rdfs:label="node"
    rdfs:comment="The rdf:ID of the target node of the edge"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/&gt;
 &lt;/rdf:Property&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>

</div>


<div class="local-name()">

<h2>6 RGML Examples</h2>

<div class="local-name()">

<h3>6.1 Simple Graph Example</h3>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" border="1" align="center" width="40%">
<tr>
<td><a name="sgraph"></a>
<h5>Figure 1: Simple Graph Example</h5>
<img alt="simple graph" src="simpleg.gif">

</td>
</tr>
</table>
</object>
<p>
This is a simple graph with three nodes and two edges. See Figure <a href="#sgraph">1</a> for a graphical representation of this simple graph.
<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
&lt;?xml version="1.0" encoding="utf-8"?&gt; 

&lt;rdf:RDF 
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
  xmlns="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:rgml="http://purl.org/puninj/2001/05/rgml-schema#"
&gt; 

&lt;Graph rdf:ID="g1" rgml:directed="true"&gt;
   &lt;nodes&gt;
      &lt;rdf:Bag&gt;
         &lt;rdf:li resource="#n1"/&gt;
         &lt;rdf:li resource="#n2"/&gt;
         &lt;rdf:li resource="#n3"/&gt;
      &lt;/rdf:Bag&gt;
   &lt;/nodes&gt;

   &lt;edges&gt;
      &lt;rdf:Bag&gt;
         &lt;rdf:li resource="#e1"/&gt;
         &lt;rdf:li resource="#e2"/&gt;
      &lt;/rdf:Bag&gt;
   &lt;/edges&gt;
&lt;/Graph&gt;

&lt;Node rdf:ID="n1"/&gt;
&lt;Node rdf:ID="n2"/&gt;
&lt;Node rdf:ID="n3"/&gt;

&lt;Edge rdf:ID="e1"&gt;
    &lt;source rdf:resource="#n1"/&gt;
    &lt;target rdf:resource="#n2"/&gt;
&lt;/Edge&gt;
&lt;Edge rdf:ID="e2"&gt;
    &lt;source rdf:resource="#n1"/&gt;
    &lt;target rdf:resource="#n3"/&gt;
&lt;/Edge&gt;

&lt;/rdf:RDF&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>


</div>


<div class="local-name()">

<h3>6.2 Webgraph Example</h3>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" border="1" align="center" width="40%">
<tr>
<td><a name="webgraph"></a>
<h5>Figure 2: Webgraph Example</h5>
<img alt="webgraph" src="webgraph.gif">

</td>
</tr>
</table>
</object>
<p>
This graph is a webgraph where the two nodes represent two web pages and the 
edges represent the hyperlinks between these web pages. We used 
the Dublin Core vocabulary to add properties to the nodes, such as dc:title, dc:format, and dc:date. The dc:title indicates the title of the web page, the 
dc:format indicates the mime type of the web page, and the dc:date indicates the date of creation of the web page. The rgml:weight property indicates the 
size in bytes of the web page. The rgml:label of the node is used to hold the URL of the web page and the rgml:label of the edge is used to hold the anchor 
text of the hyperlink. See Figure <a href="#webgraph">2</a> for a graphical representation of this webgraph.
<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
&lt;?xml version="1.0" encoding="utf-8"?&gt; 

&lt;rdf:RDF 
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
  xmlns="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:rgml="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:dc="http://purl.org/dc/elements/1.1/"&gt; 

&lt;Graph rdf:ID="g1" rgml:directed="true"&gt;
   &lt;nodes&gt;
      &lt;rdf:Bag&gt;
         &lt;rdf:li resource="#n1"/&gt;
         &lt;rdf:li resource="#n2"/&gt;
         &lt;rdf:li resource="#n3"/&gt;
      &lt;/rdf:Bag&gt;
   &lt;/nodes&gt;

   &lt;edges&gt;
      &lt;rdf:Bag&gt;
         &lt;rdf:li resource="#e1"/&gt;
         &lt;rdf:li resource="#e2"/&gt;
      &lt;/rdf:Bag&gt;
   &lt;/edges&gt;
&lt;/Graph&gt;

&lt;Node rdf:ID="n1" rgml:label="http://www.cs.rpi.edu/" 
      rgml:weight="3678"&gt;
  &lt;dc:title&gt;Rensselaer Computer Science Department&lt;/dc:title&gt;
  &lt;dc:date&gt;2001-03-01&lt;/dc:date&gt;
  &lt;dc:format&gt;text/html&lt;/dc:format&gt;
&lt;/Node&gt;
&lt;Node rdf:ID="n2" rgml:label="http://www.cs.rpi.edu/people/" 
      rgml:weight="10611"&gt;
  &lt;dc:title&gt;People at Rensselaer Computer Science Department&lt;/dc:title&gt;
  &lt;dc:date&gt;2001-02-26&lt;/dc:date&gt;
  &lt;dc:format&gt;text/html&lt;/dc:format&gt;
&lt;/Node&gt;
&lt;Node rdf:ID="n3" rgml:label="http://www.cs.rpi.edu/courses/"
      rgml:weight="6968"&gt;
  &lt;dc:title&gt;Courses at Rensselaer Computer Science Department&lt;/dc:title&gt;
  &lt;dc:date&gt;2001-01-25&lt;/dc:date&gt;
  &lt;dc:format&gt;text/html&lt;/dc:format&gt;
&lt;/Node&gt;

&lt;Edge rdf:ID="e1" rgml:label="Courses"&gt;
    &lt;source rdf:resource="#n1"/&gt;
    &lt;target rdf:resource="#n2"/&gt;
&lt;/Edge&gt;
&lt;Edge rdf:ID="e2" rgml:label="People"&gt;
    &lt;source rdf:resource="#n1"/&gt;
    &lt;target rdf:resource="#n3"/&gt;
&lt;/Edge&gt;

&lt;/rdf:RDF&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>6.3 RDF Graph Example</h3>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" border="1" align="center" width="40%">
<tr>
<td><a name="rdfgraph"></a>
<h5>Figure 3: RDF Graph Example</h5>
<img alt="RDF graph" src="rdfgraph.gif">

</td>
</tr>
</table>
</object>
<p>
This is the RGML description of the famous RDF Graph <b><span style="font-size:85%"><a name="fromrdf" href="#rdf">[RDF]</a></span></b> that represents the statement: "Ora Lassila is the creator of the  resource 
http://www.w3.org/Home/Lassila". See Figure <a href="#rdfgraph">3</a> for a graphical representation of this simple graph.
<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
&lt;?xml version="1.0" encoding="utf-8"?&gt; 

&lt;rdf:RDF 
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
  xmlns="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:rgml="http://purl.org/puninj/2001/05/rgml-schema#"&gt;

&lt;Graph rdf:ID="g1" rgml:directed="true"&gt;
   &lt;nodes&gt;
      &lt;rdf:Bag&gt;
         &lt;rdf:li resource="#n1"/&gt;
         &lt;rdf:li resource="#n2"/&gt;
      &lt;/rdf:Bag&gt;
   &lt;/nodes&gt;

   &lt;edges&gt;
      &lt;rdf:Bag&gt;
         &lt;rdf:li resource="#e1"/&gt;
      &lt;/rdf:Bag&gt;
   &lt;/edges&gt;
&lt;/Graph&gt;

&lt;Node rdf:ID="n1" rgml:label="http://www.w3.org/Home/Lassila"/&gt;
&lt;Node rdf:ID="n2" rgml:label="Ora Lassila"/&gt;

&lt;Edge rdf:ID="e1" rgml:label="Creator"&gt;
    &lt;source rdf:resource="#n1"/&gt;
    &lt;target rdf:resource="#n2"/&gt;
&lt;/Edge&gt;

&lt;/rdf:RDF&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>


<div class="local-name()">

<h3>6.4 Hypergraph Example</h3>

<p>
A hypergraph is defined as a set of vertices and a set of edges called hyperedges. A hyperedge is a subset of the set of vertices. If the hypergraph is 
directed the hyperedge is an ordered set of vertices and, if the hypergraph is undirected, the hyperedge is an unordered set of vertices. The following 
RGML example describes a directed hypergraph.

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
&lt;?xml version="1.0" encoding="utf-8"?&gt; 

&lt;rdf:RDF 
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
  xmlns="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:rgml="http://purl.org/puninj/2001/05/rgml-schema#"
&gt; 

&lt;Graph rdf:ID="g1" rgml:directed="true"&gt;
   &lt;nodes&gt;
      &lt;rdf:Bag&gt;
         &lt;rdf:li resource="#n1"/&gt;
         &lt;rdf:li resource="#n2"/&gt;
         &lt;rdf:li resource="#n3"/&gt;
         &lt;rdf:li resource="#n4"/&gt;
      &lt;/rdf:Bag&gt;
   &lt;/nodes&gt;

   &lt;edges&gt;
      &lt;rdf:Bag&gt;
         &lt;rdf:li resource="#e1"/&gt;
         &lt;rdf:li resource="#e2"/&gt;
      &lt;/rdf:Bag&gt;
   &lt;/edges&gt;
&lt;/Graph&gt;

&lt;Node rdf:ID="n1"/&gt;
&lt;Node rdf:ID="n2"/&gt;
&lt;Node rdf:ID="n3"/&gt;
&lt;Node rdf:ID="n4"/&gt;


&lt;Edge rdf:ID="e1"&gt;
    &lt;source rdf:resource="#n1"/&gt;
    &lt;target rdf:resource="#n2"/&gt;
&lt;/Edge&gt;

&lt;Edge rdf:ID="e2"&gt;
   &lt;nodes&gt;
      &lt;rdf:Seq&gt;
         &lt;rdf:li resource="#n2"/&gt;
         &lt;rdf:li resource="#n3"/&gt;
         &lt;rdf:li resource="#n4"/&gt;
      &lt;/rdf:Seq&gt;
   &lt;/nodes&gt;
&lt;/Edge&gt;

&lt;/rdf:RDF&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>

</div>

<div class="local-name()">

<h2>7 Adding graph rules using RGML and Logic primitives</h2>

<p>
Tim Berners-Lee has designed a new language, Notation 3 <b><span style="font-size:85%"><a name="fromnot3" href="#not3">[NOT3]</a></span></b>,
to describe the RDF data model. Using Notation 3, we can add logic primitives to
RGML to generate RDF properties that are commonly  used to describe graph 
information such as, cycle, adjacent, path, etc. We
will add simple rules to define two graph concepts: adjacency and paths
between nodes. The latter is a modification of the example given by the 
Euler proof engine <b><span style="font-size:85%"><a name="fromeuler" href="#euler">[EULER]</a></span></b>. 
</p>

<p>
Two nodes are adjacent if they are connected by an edge. This can be expressed
using two simple rules, where e is an edge, and u and v are nodes:
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
forall (e, u, v) : source(e,u) and target(e,v) -&gt; adjacent(u,v) 
forall (u,v) : adjacent(u,v) -&gt; adjacent(v,u) 
</pre>
</td>
</tr>
</table>
</object>
</p>

<p>
Using Notation 3 we can express these rules as:
</p>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
@prefix rdf: &lt;http://www.w3.org/1999/02/22-rdf-syntax-ns#&gt; .
@prefix rdfs: &lt;http://www.w3.org/2000/01/rdf-schema#&gt; .
@prefix rgml: &lt;http://purl.org/puninj/2001/05/rgml-schema#&gt; .
@prefix log: &lt;http://www.w3.org/2000/10/swap/log#&gt; .
@prefix : &lt;rgml_rules#&gt; .

:adjacent  rdfs:domain rgml:Node; rdfs:range rgml:Node.

{{:e rgml:source :u. :e rgml:target :v.} log:implies { :u :adjacent :v } } 
    a log:Truth; log:forAll :e, :u, :v.
{{ :u :adjacent :v. } log:implies { :v :adjacent :u. }; } 
   a log:Truth; log:forAll :u, :v.
</pre>
</td>
</tr>
</table>
</object>
</p>


<p>
A path is a sequence of consecutive nodes in a graph. Two nodes, u and v, 
are said to be consecutive if there is a directed edge from u to v, where
u is the parent of v (rule 1). The second rule states that if the node u 
is the parent of the node v, there is a directed path from u to v. The
third, a recursive rule, states the condition for the existence of a path
from nodes u to w.  These three rules are the following 
(where u, v, w are nodes; e is an edge and g is a graph) :
</p>


<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
forall (g,e,u,v) : g is directed and source(e,u) and target(e,v) -&gt; parent(u,v) 
forall (g,u,v) : g is directed and parent(u,v) -&gt; path(u,v) 
forall (g,u,v,w) : g is directed and parent(u,v) and path(v,w) -&gt; path(u,w) 
</pre>
</td>
</tr>
</table>
</object>
</p>


<p>
Using Notation 3 we can express these rules as:
</p>


<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
@prefix rdf: &lt;http://www.w3.org/1999/02/22-rdf-syntax-ns#&gt; .
@prefix rdfs: &lt;http://www.w3.org/2000/01/rdf-schema#&gt; .
@prefix rgml: &lt;http://purl.org/puninj/2001/05/rgml-schema#&gt; .
@prefix log: &lt;http://www.w3.org/2000/10/swap/log#&gt; .
@prefix : &lt;rgml_rules#&gt; .

:parent  rdfs:domain rgml:Node; rdfs:range rgml:Node.
:path  rdfs:domain rgml:Node; rdfs:range rgml:Node.

{{ :g rgml:directed "true". :e rgml:source :u. :e rgml:target :v.} 
   log:implies { :u :parent :v. }; } 
   a log:Truth; log:forAll :e, :u, :v , :g.

{{ :g rgml:directed "true". :u :parent :v} 
   log:implies {:u :path :v}} 
   a log:Truth; log:forAll :g, :u, :v.

{{ :g rgml:directed "true". :u :parent :v. :v :path :w} 
   log:implies {:u :path :w}} 
   a log:Truth; log:forAll :g, :u, :v, :w.
</pre>
</td>
</tr>
</table>
</object>
</p>



<p>
To express the rules we use the logic properties log:implies and log:forAll
that are part of the logic schema <b><span style="font-size:85%"><a name="fromnot3" href="#not3">[NOT3]</a></span></b> . We use the cwm
engine <b><span style="font-size:85%"><a name="fromcwm" href="#cwm">[CWM]</a></span></b> to process these rules on a simple graph 
expressed in RGML. 
</p>


</div>

<div class="local-name()">

<h2>8 Conclusion</h2>

<p>
In this paper, we defined a new RDF vocabulary (RGML) to describe the 
structure and semantics of graphs. We showed how to combine different 
vocabularies in order to add rich metadata to the graph components, and
we defined logic rules to express graph properties. We are currently 
expanding our logic rules to express many other graph properties. 
Future RGML modules will add new vocabularies to describe different types 
of graphs, such as webgraphs, network graphs, organization charts, 
UML graphs, etc. 
</p>

</div>

<div class="local-name()">

<h2>9 RDF/XML Serialization of the RGML RDF Schema</h2>

<p>

<br class="br">
<object>
<table bgcolor="#BADABA" cellpadding="8" align="center" width="80%" border="1">
<tr>
<td>
<pre>
&lt;?xml version="1.0" ?&gt; 
&lt;!-- 
     RDF Schema declaration for RDF Graph Modeling Language (RGML) 1.0 
     &lt;http://purl.org/puninj/2001/05/rgml-schema#&gt;
--&gt;
&lt;rdf:RDF 
     xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
     xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#"&gt;

&lt;!-- Class Declarations --&gt;

&lt;!-- Graph Class declaration --&gt;

  &lt;rdfs:Class rdf:ID="Graph" 
    rdfs:label="Graph"
    rdfs:comment="A Graph Description"&gt;
    &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt;
  &lt;/rdfs:Class&gt;

&lt;!-- Node Class declaration --&gt;

  &lt;rdfs:Class rdf:ID="Node" 
    rdfs:label="Node"
    rdfs:comment="A Node Description"&gt;
    &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt;
  &lt;/rdfs:Class&gt;

&lt;!-- Edge Class declaration --&gt;

  &lt;rdfs:Class rdf:ID="Edge" 
    rdfs:label="Edge"
    rdfs:comment="An Edge Description"&gt;
    &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt;
  &lt;/rdfs:Class&gt;

&lt;!-- Property declarations --&gt;

&lt;!-- Global Properties --&gt;

 &lt;rdf:Property ID="label"
    rdfs:label="label"
    rdfs:comment="Text representation of the graph elements"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Node"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/&gt;
 &lt;/rdf:Property&gt;

&lt;!-- Graph Properties --&gt;

 &lt;rdf:Property ID="directed"
    rdfs:label="directed"
    rdfs:comment="Boolean value to indicate whether the Graph is directed or not"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#boolean"/&gt;
 &lt;/rdf:Property&gt;

 &lt;rdf:Property ID="nodes"
   rdfs:label="Nodes"
   rdfs:comment="List of the nodes belong to the graph"&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Resource"/&gt;
 &lt;/rdf:Property&gt;

 &lt;rdf:Property ID="edges"
   rdfs:label="Edges"
   rdfs:comment="List of the edges belong to the graph"&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Bag"/&gt;
 &lt;/rdf:Property&gt;

 &lt;rdf:Property ID="graphs"
   rdfs:label="Subgraphs"
   rdfs:comment="List of subgraphs belong to the graph"&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Bag"/&gt;
 &lt;/rdf:Property&gt;

&lt;!-- Node Properties --&gt;

 &lt;rdf:Property ID="weight"
    rdfs:label="weight"
    rdfs:comment="Value (usually numerical) to show the node or edge weight"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Node"/&gt;
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/&gt;
 &lt;/rdf:Property&gt;

&lt;!-- Edge Properties --&gt;

 &lt;rdf:Property ID="source"
    rdfs:label="source"
    rdfs:comment="The rdf:ID the source node of the edge"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/&gt;
 &lt;/rdf:Property&gt;

 &lt;rdf:Property ID="target"
    rdfs:label="target"
    rdfs:comment="The rdf:ID of the target node of the edge"&gt;
   &lt;rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/&gt; 
   &lt;rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/&gt;
   &lt;rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/&gt;
 &lt;/rdf:Property&gt;

&lt;/rdf:RDF&gt;
</pre>
</td>
</tr>
</table>
</object>
</p>

</div>



<hr>

<h3>
<i>Bibliography</i>
</h3>
<p>

<b><a name="cwm" href="#fromcwm">[CWM] </a></b>
 Tim Berners-Lee. Semantic Web Area for Play : Closed World Machine. http://www.w3.org/2000/10/swap/Overview.html, February, 2001. 
</p>
<p>

<b><a name="daml" href="#fromdaml">[DAML] </a></b>
 DARPA Agent Markup Language (DAML). http://www.daml.org/ 
</p>
<p>

<b><a name="dc">[DC] </a></b>
 S. Weibel, J.Kunze, C. Lagoze, and M. Wolf. Dublin Core Metadata for Resource Discovery, Internet RFC 2413. http://purl.oclc.org/dc/, 1998. 
</p>
<p>

<b><a name="euler">[EULER] </a></b>
 Jos De Roo. Euler proof mechanism. http://www.agfa.com/w3c/euler/, June, 2001 . 
</p>
<p>

<b><a name="graphxml">[GRAPHXML] </a></b>
 Herman I, Marshall MS. GraphXML - An XML-based graph description format. <i>Proceedings of the Symposium on Graph Drawing</i>, 2000; 52-62 
</p>
<p>

<b><a name="gxl">[GXL] </a></b>
 R. C. Holt, A. Winter, A. Schurr. GXL: Towards a Standard Exchange Format
<i>Proceedings 7th Working Conference on Reverse Engineering</i> (WCRE 2000)
</p>
<p>

<b><a name="not3" href="#fromnot3">[NOT3] </a></b>
 Tim Berners-Lee. Notation 3. http://www.w3.org/DesignIssues/Notation3.html, April, 2001. 
</p>
<p>

<b><a name="rdf" href="#fromrdf">[RDF] </a></b>
 O. Lassila and R. Swick. W3C, Resource Description Framework (RDF) Model and Syntax Specification . http://www.w3.org/TR/REC-rdf-syntax, 1999. 
</p>
<p>

<b><a name="rdfs">[RDFS] </a></b>
 D. Brickley and R.V. Guha. W3C, Resource Description Framework (RDF) Schema Specification 1.0. http://www.w3.org/TR/rdf-schema/, 2000. 
</p>
<p>

<b><a name="wwwpal" href="#fromwwwpal">[WWWPAL] </a></b>
 J. Punin, M. Krishnamoorthy. WWWPal System - A System for Analysis and Synthesis of Web Pages. In <i>Proceedings of
the WebNet 98 Conference</i>, Orlando, November, 1998. 
</p>
<p>

<b><a name="xgmml">[XGMML] </a></b>
 J. Punin, M. Krishnamoorthy. XGMML, Extensible Graph Markup and Modeling Language Specification, 1999.
http://www.cs.rpi.edu/~puninj/XGMML/draft-xgmml.html 

</p>
<p>

<b><a name="xml" href="#fromxml">[XML] </a></b>
 T. Bray, J. Paoli and C. M. Sperberg-McQueen, Extensible Markup Language (XML 1.0) - http://www.w3.org/TR/REC-xml, 2000. 
</p>
<p>

<b><a name="xmlns">[XMLNS] </a></b>
 T. Bray, D. Hollander and A. Layman. Namespaces in XML,  http://www.w3.org/TR/REC-xml-names, 1999. 
</p>
<p>

<b><a name="xmlschema">[XMLSCHEMA] </a></b>
 H. Thompson et al. XML Schema Part 1: Structures.
http://www.w3.org/TR/xmlschema-1, 2001. 
</p>
<hr>
<a href="index.html"><img alt="back" src="lfarrw.gif"></a>
<hr>
</body>
</html>
